1. Field of the Invention
The invention pertains generally to computer processing. In particular, it pertains to obtaining accurate results when using integer averaging instructions that are inherently inaccurate because they round off the results.
2. Description of the Related Art
Many applications have been found in the computer field that involve averaging multiple numbers together. One such application is in the motion compensation (MC) algorithms used for encoding and decoding compressed digital data in the processing of moving video images. Basically, the MC operation includes a way to generate various pixels in a video frame being constructed, called the destination frame, based on related pixels from one or more reference frames. Averaging pixel values from the reference frame(s) is part of that process. Such averaging may reduce the information content in the resulting image, but this loss is more than compensated for by greatly reducing the amount of storage space required to store the video images and the amount of bandwidth required to transmit the video images.
FIG. 1 shows an example of representative pixel averaging. Block 11 is a block of pixels (also called pels) in a larger reference frame. Close-up view 12 shows an enlargement of four pixels a, b, c and d in the upper left corner of block 11. The values of these four pixels are averaged together to produce a single pixel e, shown in close-up view 13, which becomes the upper left pixel in block 16 of the destination frame. Typically, the values of all these pixels are represented as unsigned integers. Blocks 11 and 16 may contain different numbers of pixels.
This motion mode process is frequently referred to as xe2x80x9chalf-pel horizontally and half-pel verticallyxe2x80x9d, or simply xe2x80x9chalf-half pelxe2x80x9d. In general, other averaging modes can be used such as xe2x80x9chalf-pel horizontalxe2x80x9d prediction that averages two horizontally adjacent pixels, and xe2x80x9chalf-pel verticalxe2x80x9d prediction that averages two vertically adjacent pixels.
A commonly used averaging operation can be defined as follows:
1. Half-pel: result=(value1+value2)//2
2. Half-half-pel: result=(value1+value2+value3+value4)//4
where xe2x80x9c//xe2x80x9d is defined as integer division with rounding to the nearest integer. Half-integer values are rounded away from zero. For example, a result of 3.5 would be rounded to 4. Since the results must be integers, the round off error from any single averaging function can produce a result that is inaccurate by as much as 0.5. This is acceptable, and even unavoidable, in the final result. But in multi-stage averaging operations, round off errors from each stage can accumulate, leading to errors in the final results that are significantly greater. Various conventional approaches have been tried to reduce the amount and/or frequency of occurrence of these errors.
Some computer instruction sets have an instruction that performs an integer averaging function between two numbers, thus permitting easy implementation of the pixel averaging function. If more than two pixels are being averaged, the operation must proceed in successive stages, potentially leading to the aforementioned accumulation of round off errors. In conventional approaches to reducing the final error, a tradeoff must be made between speed and accuracy.
One conventional approach is shown in the code and flow chart of FIGS. 2A and 2B, respectively. In a first stage, elements a and b are averaged to produce a first intermediate result avexe2x80x941, and elements c and d are averaged to produce a second intermediate result avexe2x80x942. In a second stage, the first and second intermediate results are averaged to produce a final result. This method is fast, but can produce an error of +0.5 in the first stage and an additional error of +0.5 in the second stage, resulting in an error of +1.0 in approximately 37% of the final results. The term xe2x80x98simdxe2x80x99 indicates the use of a Single Instruction Multiple Data (SIMD) instruction which simultaneously performs the same function on multiple parallel data elements in a packed format.
FIGS. 3A and 3B show the code and flow chart, respectively, of a second conventional approach that modifies the first approach by subtracting the value xe2x80x9c1xe2x80x9d from one of the intermediate results before averaging those two results together in the second stage. This artificial method of blindly compensating for expected errors reduces the probability of getting an error of +1.0 to about 13%.
FIGS. 4A and 4B show the code and flow chart, respectively, of a conventional brute force approach. All four pixel values are unpacked, added together, and divided by 4 (shifted to the right by two bits). A constant of xe2x80x982xe2x80x99 (constxe2x80x942xe2x80x944_words) is also added to compensate for the fact that shifting to the right rounds down by truncating rather than rounding up as required. This approach is accurate but slow, since it requires eight unpack operations, eight add operations, two shift operations, and one pack operation.
Thus, each of the conventional approaches to averaging pixel values is either fast but inaccurate, or accurate but slow.
An embodiment of the invention includes a method of averaging pixel values, which includes performing a first stage operation by averaging first and second pixel values to produce a first intermediate integer result, and also by averaging third and fourth pixel values to produce a second intermediate integer result. A second stage operation is performed by averaging the first and second intermediate integer results to produce a third intermediate integer result. It is detected whether the first stage operation produced an error and whether the second stage operation produced an error. If both the first and second stages produced an error, a correction value is applied to the third intermediate integer result to produce a final pixel value.